package bag;

/**
 * 0-1 背包问题
 * 背包专题
 * 题目	我的题解
 * 416. 分割等和子集	动态规划之01背包问题 反向target循环
 * 494. 目标和	动态规划之01背包问题   反向target循环
 * 322. 零钱兑换	动态规划之完全背包问题  正向target循环
 * 518. 零钱兑换 II	动态规划之完全背包的组合问题 正向target循环
 * 377. 组合总和 Ⅳ	动态规划之完全背包考虑顺序的组合问题
 *
 */

class 目标和_494_重做版 {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0 , length = nums.length;

        for(int i = 0; i < length; i ++) {
            sum += nums[i];
        }
        //  正数和为n  则 n -( sum -n) = target  => n = (sum + target) / 2  转化为求正数n  使得所有加上+号的数字 和为 (sum + target) / 2
        if( sum < target || (sum + target) % 2 == 1) return 0;
        target = Math.abs((sum + target)/ 2); //如果target为负值  转化为求正值  结果等价  那为什么不直接取加上-号的数字的和呢？？？？ ( sum -n) - n = target  => n = （sum -target）/ 2 后续重做用这个

        int[][] dp  = new int[length + 1][target + 1]; // 取＋的数字个数可能为 0 ~ nums.length    ，  和数值取值范围为  0 ~ target
        dp[0][0] = 1; // 1个都不取 和为 0 的种类数为1  其他dp[0][i] = 0 ； dp[i][0]在递推过程中求得
        for(int i = 1; i<= length; i++) {
            for(int j =0; j<= target; j ++ ) {
                int x = nums[i - 1];
                // 求和为j  每个数字有取或者不取两种
                if(x <= j) dp[i][j] += dp[i - 1][j - x]; // 取nums[i]
                dp[i][j] += dp[i - 1][j];// 不取nums[i]

                // 如果简化为1维滚动  可以改成 倒序   if(x <= j) dp[j] += dp[j -x]
            }
        }

        return dp[length][target];
    }
}


public class 目标和_494 {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        int zeroCount = 0;
        for(int num : nums) {
            sum += num;
            if(num == 0)
                zeroCount ++;
        }
        if(sum < Math.abs(target)) return 0;
        if ((sum - target) % 2 == 1) return 0;
        // 转换为背包问题  前i个  有多少种选法  能使和为target
        target = (sum - target) / 2;

        int[][] dp = new int[nums.length + 1][ target + 1];

        for(int i = 0; i < nums.length + 1; i++) {
            dp[i][0] = 1;
        }
        // 若num = 0  不能这样写边界条件
        /*for(int j = 1; j < target + 1; j ++) {
            dp[0][j] = 0;
        }*/

        for(int i = 1; i < nums.length + 1; i++) {
            for(int j = 0 ; j< target + 1; j++) {
                if(nums[i - 1] > j) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    // 不选能组成j的方法  选能组成j的方法
                    dp[i][j] = dp[i-1][j] + dp[i-1][j - nums[i - 1]];
                }
            }
        }
        return dp[nums.length][target]  ;
    }
}
